package com.heima.leetcode.practice;

import java.util.Arrays;

/**
 * @description: leetcode 279. 完全平方数
 * @author 勾新杰
 * @version 1.0
 * @date 2025/2/13 0:28
 */
public class E279 {

    /**
     * <h3>方法一：动态规划</h3>
     * @param n 目标值
     * @return 最少完全平方数的个数
     */
    public int numSquares1(int n) {
        // 初始化 dp 数组
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE); // 初始化为最大值
        dp[0] = 0; // 组成 0 需要 0 个完全平方数
        // 遍历 1 到 n
        for (int i = 1; i <= n; i++) {
            // 遍历所有可能的完全平方数
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }

    /**
     * <h3>方法二：数学推导</h3>
     * 四平方和定理指出，任何一个正整数都可以表示为不超过 4 个完全平方数的和。
     * 因此，我们可以通过数学方法快速判断结果是否为 1、2、3 或 4。
     * @param n 目标值
     * @return 最少完全平方数的个数
     */
    public int numSquares2(int n) {
        // 1. 首先检查 n 是否是完全平方数，如果是，返回 1。
        if (isSquare(n)) return 1;
        // 2. 然后检查 n 是否可以表示为两个完全平方数的和，如果是，返回 2。
        for (int i = 1; i * i <= n; i++)
            if (isSquare(n - i * i))
                return 2;
        // 3. 接着检查 n 是否满足 n = 4^k * (8m + 7)，如果是，返回 4。
        while (n % 4 == 0) n /= 4;
        if (n % 8 == 7) return 4;
        // 4. 否则返回 3
        return 3;
    }

    /**
     * 判断一个数是否为完全平方数
     * @param n 要判断的数
     * @return true 表示是完全平方数，false 表示不是完全平方数
     */
    private boolean isSquare(int n) {
        int sqrt = (int) Math.sqrt(n);
        return sqrt * sqrt == n;
    }
}
